package g

/*
 * @lc app=leetcode.cn id=30 lang=golang
 *
 * [30] 串联所有单词的子串
给定一个字符串 s 和一些 长度相同 的单词 words 。
找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

1 <= s.length <= 104     s 由小写英文字母组成
1 <= words.length <= 5000
1 <= words[i].length <= 30   words[i] 由小写英文字母组成

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
*/

// @lc code=start
func findSubstring(s string, words []string) []int {
	return findSubstring1(s, words)
}

// findSubstring1 包里，使用一个map存储words,workd[i]作为key，value等于个数，
func findSubstring1(s string, words []string) []int {
	if len(words) == 0 {
		return []int{0}
	}
	wordLen := len(words[0])
	if len(s) < wordLen*len(words) {
		return nil
	}
	wordsMap := make(map[string]int)
	for i := 0; i < len(words); i++ {
		if val, ok := wordsMap[words[i]]; ok {
			wordsMap[words[i]] = val + 1
		} else {
			wordsMap[words[i]] = 1
		}
	}
	var results []int
	for i := 0; i < len(s); i++ {
		newWordsMap := make(map[string]int)
		if i+len(words)*wordLen > len(s) {
			break
		}

		findStr := true
		for j := i; j < i+len(words)*wordLen; j += wordLen {
			wantWord := s[j : j+wordLen]
			if val, ok := wordsMap[wantWord]; ok {
				if _, ok := newWordsMap[wantWord]; ok {
					newWordsMap[wantWord]++
					if newWordsMap[wantWord] > val {
						findStr = false
						break
					}
				} else {
					newWordsMap[wantWord] = 1
				}
			} else {
				findStr = false
				break
			}
		}
		if findStr {
			results = append(results, i)
		}
	}

	return results
}

// @lc code=end
